#pragma once
#include "rbtree.hpp"
#include <utility>

namespace test
{

template<class K, class V, class Compare = less<K>>
class map
{
private:
public:
    struct KeyOfVal
    {
        const K& operator()(const pair<const K, V>& kv)
        {
            return kv.first;
        }
    };

public:
    typedef rb_tree<K, pair<const K, V>, KeyOfVal, Compare> rep_type;
    typedef typename rep_type::iterator iterator;
    typedef typename rep_type::const_iterator const_iterator;

public:
    iterator find(const K& key)
    {
        return _t.find(key);
    }

    pair<iterator, bool> insert(const pair<const K, V>& kv)
    {
        return _t.insert(kv);
    }

    V& operator[](const K& key)
    {
        return _t.insert(make_pair(key, V())).first->second;
    }

    void inorder()
    {
        _t.inorder();
    }

public:
    iterator begin()
    {
        return _t.begin();
    }

    iterator end()
    {
        return _t.end();
    }

private:
    rep_type _t;
};

void test_map_1()
{
    map<string, string> dict;

    dict.insert(pair<string, string>("i", "wo"));
    dict.insert(make_pair("is", "shi"));
    dict.insert({"sort", "paixu"});
    auto ret = dict.insert({"sort", "[[paixu]]"});
    // pair<iterator, bool>
    cout <<(ret.first)->first << (ret.first)->second << ret.second << endl;
    cout << (*ret.first).first << endl;

    string str;
    while (cin >> str)
    {
        map<string, string>::iterator it = dict.find(str);
        if (it != dict.end())
        {
            cout << it->first << "-" << it->second << endl;
        }
    }
}

void test_map_2()
{
    string arr[]
        = {"xg","xg","pg","xg","pg","pg","xg","pg","xj","pg","xj","li"};

    map<string, int> count_map;
    for (auto& e : arr)
    {
        map<string, int>::iterator ret = count_map.find(e);
        if (ret == count_map.end())
        {
            count_map.insert(make_pair(e, 1));
        }
        else
        {
            ret->second++;
        }
    }

    for (auto& e : arr)
    {
        count_map[e]++;
    }

    count_map["tz"];
    cout << count_map["pg"];
    count_map["pg"] = 111;
    count_map["mht"] = 888;

    for (auto& kv: count_map)
    {
        cout << kv.first << ": " << kv.second << endl;
    }
}

void test_map_3()
{
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int b[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};

    test::map<int, int> m1;
    test::map<int, int> m2;
    for (auto e : a)
    {
        m1.insert(make_pair(e, e));
    }

    for (auto e : b)
    {
        m2.insert(make_pair(e, e));
    }

    m1.inorder();
    m2.inorder();
}

}